package sorting;

import java.util.Arrays;
import java.util.Random;

public class CountingSort {
	static void sort(int[] a, int k) {
		int size = a.length;
		int[] b = new int[k];
		for (int in : a) {
			b[in]++;
		}
		int temp = 0;
		for (int i = 0; i < b.length; i++) {
			b[i] += temp;
			temp = b[i];
		}
		System.out.println(Arrays.toString(b));
		int[] c = new int[size];
		for (int j = a.length - 1; j >= 0; j--) {
			c[--b[a[j]]]=a[j];
		}
		System.out.println(Arrays.toString(c));
	}

	public static void main(String[] args) {
		int size = 10;
		int k = 20;
		Random rand = new Random();
		int[] a = new int[size];
		for (int i = 0; i < size; i++)
			a[i] = rand.nextInt(k);
		System.out.println(Arrays.toString(a));
		sort(a, k);
	}
}
